package subject_set.top101;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/11/01 17:53
 **/
public class BM23 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public class Solution {
        List<Integer> list = new LinkedList<>();
        public int[] preorderTraversal (TreeNode root) {
            preOrder(root);
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
        private void preOrder(TreeNode root){
            if(root == null) return;
            list.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public class Solution2 {
        public int[] preorderTraversal (TreeNode root) {
            if(root == null) return new int[0];
            List<Integer> list = new LinkedList<>();
            Deque<TreeNode> s = new LinkedList<>();
            s.push(root);
            while(!s.isEmpty()){
                TreeNode cur = s.pop();
                list.add(cur.val);
                if(cur.right != null) s.push(cur.right);
                if(cur.left != null) s.push(cur.left);
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }
}